package leetcode

//https://leetcode.com/problems/merge-k-sorted-lists/

fun main(args: Array<String>) {

}

//TODO 待改进，耗时太久 780ms   13.54%
fun mergeKLists(lists: Array<ListNode?>): ListNode? {

    var i = 0
    var node: ListNode? = null

    while (i < lists.size) {
        node = mergeK(node, lists[i])
        i++
    }
    return node

}

fun mergeK(l1: ListNode?, l2: ListNode?): ListNode? {
    if (l1 == null && l2 == null) return l1
    val result = ListNode(0)
    var p = result


    var header1 = l1
    var header2 = l2
    while (header1 != null || header2 != null) {

        if (header1 != null && header2 != null) {
            if (header1.`val` > header2.`val`) {
                p.`val` = header2.`val`
                header2 = header2.next
            } else {
                p.`val` = header1.`val`
                header1 = header1.next
            }
            p.next = ListNode(0)
            p = p.next!!
        } else {

            var h = if (header1 != null) header1 else header2

            p.`val` = h!!.`val`
            while (h?.next != null) {
                h = h.next
                p.next = ListNode(0)
                p = p.next!!
                p.`val` = h!!.`val`
            }
            break


        }
    }

    return result
}